/**
 * @see https://leetcode-cn.com/problems/edit-distance/
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  if(!word1.length) {
    return word2.length;
  }
  if(!word2.length) {
    return word1.length;
  }
  word1 = '0' + word1;
  word2 = '0' + word2;
  let s1 = word1.length;
  let s2 = word2.length;
  let dp = [];
  let i = 0;
  let j = 0;
  // 构造二维数组
  for (i = 0; i < s1; i++) {
    dp[i] = new Array(s2).fill(0);
    dp[i][0] = i;
  }
  for (j = 0; j < s2; j++) {
    dp[0][j] = j;
  }
  console.log(dp)
  /**
   * dp[i,j] = s1[i] === s2[j] ? dp[i-1,j-1]    // 当i和j位置的字符相同情况下，理解为其最大次数为前一个位置的最大次数
   * dp[i,j] = s1[i] !== s2[j] ? [增加，删除，修改]
   * 增加：s1新增字符与s2[j]相同，则是s[i+1] = s[j]，按照上述推断，其值为dp[i-1, j-1]，则推断出dp[i,j] = dp[i, j-1] + 1;
   * 删除：s1删除字符i与s2[j]相同，则是s[i-1] = s[j]，按照上述推断，其值为dp[i-2, j-1]，则推断出dp[i,j] = dp[i-1, j] + 1;
   * 替换：s1替换字符i与s2[j]相同，则s1[i] = s2[j]，按照上述推断，其值为dp[i-1, j-1]，推断出dp[i,j] = dp[i-1,j-1] + 1
   */
  for (i = 1; i < s1; i++) {
    const v1 = word1[i];
    for (j = 1; j < s2; j++) {
      const v2 = word2[j];
      if (v1 == v2) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        let add = dp[i][j - 1] + 1;
        let del = dp[i - 1][j] + 1;
        let rep = dp[i - 1][j - 1] + 1;
        dp[i][j] = Math.min.apply(null, [add, del, rep])
      }
    }
  }
  console.log(dp)
  return dp[i - 1][j - 1];
};

minDistance('horse', 'ros');
// "horse"
// "ros"